1. Field of the Invention
The present invention is directed to computer systems. More particularly, it is directed to image processing.
2. Description of the Related Art
Water is crucial to human life. People see, use and drink water every day, thus it is not surprising that water simulation plays an important role in computer graphics. Incompressible fluid dynamics, including water movement, in general can be described by the Navier-Stokes equations. These complex differential equations describe the motion of fluids in terms of the relationships among the rates of change of certain variables of interest (e.g., gravity, pressure, viscous forces). The solution to the equations indicates not position, but velocity, (e.g., a velocity field or flow field), from which other properties may be derived (e.g., path, flow rate, drag). Graphics researchers have invented and adopted many numerical methods to generate various realistic water effects by solving the Navier-Stokes equations ever since water animation was introduced into the graphics community during the 1980's. Most previous research has been focused on simulating the high-speed dynamics of large bodies of water. However, providing a fast and accurate technique to simulate small-scale fluid dynamics (e.g., relatively calm water) and its interaction with solid surfaces, such as toy boats floating in a bathtub and water drops streaming down a glass, has not been adequately addressed. Previous height-field-based techniques only supported a limited range of effects. In particular surface tension forces were neglected. This omission diminished the accuracy of small-scale liquid simulations, in which surface tension may be a dominant force affecting the shape of the liquid.
Water animation is notoriously difficult and time-consuming to produce because solving three-dimensional (3D) Navier-Stokes equations requires a huge computational domain. Traditionally, two basic approaches to simulating fluid dynamics have been applied: a Euclidean approach (in which fluid motion is solved with respect to a fixed grid), and a Lagrangian approach (in which particle advection is computed and the fluid is reconstructed according to the physics of the particles). Both memory and computational costs increase at least cubically in three dimensions when water is represented either by particle systems or 3D grid systems. To improve simulation performance, some prior techniques have attempted to reduce the computational space. For example, instead of using completely uniform grids in 3D, the use of non-uniform grids, such as octree structures or cells with various lengths, has been proposed. Others have considered solving fluid dynamics on unstructured tetrahedral meshes rather than grid structures. Principal Component Analysis (PCA) has been used to further reduce a static computational space. However, it is difficult to extend this method to free surface water animations.
Height fields have been introduced to the graphics community for rapid fluid simulations. For a description of the use of height fields, see, e.g., Kass, M., and Miller, G., “Rapid, Stable Fluid Dynamics for Computer Graphics” Proc. of ACM SIGGRAPH 1990 (hereinafter “Kass and Miller 1990”), which is herein incorporated by reference in its entirety. The method described therein for animating water is based on an approximation to the shallow water equations that involves a version of the wave equation on a height field in which the wave velocity is proportional to the square root of the depth of the water. The resulting wave equation is then solved using an alternating-direction implicit method on a uniform finite-difference grid.
The computational domain of a height-field-based system increases only quadratically with the spatial resolution. This technique was later augmented with semi-Lagrangian velocity advection. In general, advection refers to transport in a fluid, and simulations of advection typically look back along the velocity vector of the fluid at a point of interest to determine what will arrive at the point of interest in the future. For example, see Layton, A. T., and Van de Panne, M., “A Numerically Efficient and Stable Algorithm for Animating Water Waves” The Visual Computer (2002) 18:41-53, which is herein incorporated by reference in its entirety. The algorithm described therein is based on two-dimensional (2D) shallow water equations integrated using an implicit semi-Lagrangian scheme that allows large time steps while maintaining stability.
Instead of using shallow wave equations, some researchers have proposed to solve pressure projection only in two dimensions, while solving other simulation steps in three dimensions. Techniques to combine a height field representation with a grid structure in order to simulate some non-height-field behaviors, such as overturning and splashing, have also been demonstrated. As mentioned above, previous height-field-based techniques only supported a limited range of effects.
In order to simulate two-dimensional water flows on curved surfaces, the use of quadrilateral meshes from Catmull-Clark subdivision has been proposed. Flow simulation directly on manifold triangle meshes has been demonstrated using discrete differential geometry (DDG) operators. The “Back and Forth Error Compensation and Correction” (BFECC) method has been further adopted to reduce numerical dissipation in surface flows.
Other related topics include water wave simulation, height-field-based painting systems, fluid surface tension (and its contact angle), highly viscous liquids and viscoelastic liquids, and fluid control.